package map;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Leedcode219存在重复元素II {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        //遍历数组，将数组中相同元素的保存在hash表中
        Map<Integer, ArrayList<Integer>> hashtable = new HashMap<>();
        //K为nums[i] ，V:下标
        for (int i = 0; i < nums.length; i++) {

            if (hashtable.containsKey(nums[i])){
                ArrayList<Integer> array = hashtable.get(nums[i]);
                array.add(i);
            }else {
                ArrayList<Integer> list = new ArrayList();
                list.add(i);
                hashtable.put(nums[i],list);
            }
        }
        //此时全部元素都已经按照值，将下标保存到表中
        for (Map.Entry<Integer, ArrayList<Integer>> entry : hashtable.entrySet()) {
            ArrayList<Integer> list = entry.getValue();
            if (list.size() > 1){
                Object[] array =  list.toArray();
                for (int i = 0; i < array.length; i++) {
                    for (int j = i + 1; j < array.length ; j++) {
                        if ((Integer)array[j] - (Integer) array[i] <= k){
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Leedcode219存在重复元素II o = new Leedcode219存在重复元素II();
        int[] arr = {1,2,3,1,2,3};
        System.out.println(o.containsNearbyDuplicate(arr, 2));
    }
}
